package com.jjlin.leetcode.biweekly_contest.no40_2020_11_28;

public class Solution4 {
    //得到山形数组的最少删除次数
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        if(n < 3)
            return 0;
        int[] f = new int[n]; //f[i]表示nums[i]左边的子串中以nums[i]结尾的最长上升子序列的长度
        int[] g = new int[n]; //g[i]表示nums[i]右边的子串中以nums[i]开头的最长下降子序列的长度
        for(int i = 0; i < n; i++){
            f[i] = 1;
            for(int j = 0; j < i; j++)
                if(nums[j] < nums[i])
                    f[i] = Math.max(f[i], f[j] + 1);
        }

        for(int i = n - 1; i >= 0; i--){
            g[i] = 1;
            for(int j = n - 1; j > i; j--){
                if(nums[j] < nums[i])
                    g[i] = Math.max(g[i], g[j] + 1);
            }
        }

        int res = 0;
        for(int i = 0; i < n; i++){
            if(g[i] > 1 && f[i] > 1) //要保证每个子序列的长度都要大于1
                res = Math.max(res, g[i] + f[i] - 1); //注意要减去1，因此nums[i]在上升子序列和下降子序列中都包含
        }

        return n - res; //山形数组的最少删除次数
    }
}
